package main

import "fmt"

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

func createTree(treeValList []interface{}) *TreeNode {
	if len(treeValList) == 0 {
		return nil
	}
	treeNodeList := []*TreeNode{nil}
	for _, treeVal := range treeValList {
		if treeVal == nil {
			treeNodeList = append(treeNodeList, nil)
		} else {
			treeNodeList = append(treeNodeList, &TreeNode{Val: treeVal.(int)})
		}
	}
	n := len(treeNodeList)
	for i := range treeNodeList {
		if treeNodeList[i] == nil {
			continue
		}
		if 2*i < n {
			treeNodeList[i].Left = treeNodeList[2*i]
		}
		if 2*i+1 < n {
			treeNodeList[i].Right = treeNodeList[2*i+1]
		}
	}
	return treeNodeList[1]
}

func dfs(root *TreeNode, sum int) int {
	if root == nil {
		return 0
	}
	sum = sum*10 + root.Val
	if root.Left == nil && root.Right == nil {
		return sum
	}
	return dfs(root.Left, sum) + dfs(root.Right, sum)
}

func sumNumbers(root *TreeNode) int {
	return dfs(root, 0)
}

func main() {
	fmt.Println(sumNumbers(createTree([]interface{}{1, 2, 3})))
}
